<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  
  
  <link rel="shortcut icon" href="../../img/favicon.ico">
  <title>0126 word ladder ii - 力扣问题题解（简易版）</title>
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Lato:400,700|Roboto+Slab:400,700|Inconsolata:400,700" />

  <link rel="stylesheet" href="../../css/theme.css" />
  <link rel="stylesheet" href="../../css/theme_extra.css" />
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/github.min.css" />
  
  <script>
    // Current page data
    var mkdocs_page_name = "0126 word ladder ii";
    var mkdocs_page_input_path = "\u5e7f\u5ea6\u4f18\u5148\u904d\u5386/0126-word-ladder-ii.md";
    var mkdocs_page_url = null;
  </script>
  
  <script src="../../js/jquery-2.1.1.min.js" defer></script>
  <script src="../../js/modernizr-2.8.3.min.js" defer></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script> 
  
</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
    <div class="wy-side-scroll">
      <div class="wy-side-nav-search">
        <a href="../.." class="icon icon-home"> 力扣问题题解（简易版）</a>
        <div role="search">
  <form id ="rtd-search-form" class="wy-form" action="../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" title="Type search term here" />
  </form>
</div>
      </div>

      <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../..">Welcome to MkDocs</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">广度优先遍历</span></p>
                <ul class="current">
                    <li class="toctree-l1 current"><a class="reference internal current" href="./">0126 word ladder ii</a>
    <ul class="current">
    </ul>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../0127-word-ladder/">0127 word ladder</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">第 2 章 排序算法</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/0001-two-sum/">0001 two sum</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/0011-container-with-most-water/">0011 container with most water</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/">归并排序</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/">插入排序</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/">选择排序</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">第 3 章 二分查找</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%203%20%E7%AB%A0%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/0035-search-insert-position/">0035 search insert position</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%203%20%E7%AB%A0%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/0153-find-minimum-in-rotated-sorted-array/">0153 find minimum in rotated sorted array</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%203%20%E7%AB%A0%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/0154-find-minimum-in-rotated-sorted-array-ii/">0154 find minimum in rotated sorted array ii</a>
                    </li>
                </ul>
      </div>
    </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" role="navigation" aria-label="top navigation">
        <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
        <a href="../..">力扣问题题解（简易版）</a>
      </nav>

      
      <div class="wy-nav-content">
        <div class="rst-content">
          <div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="../..">Docs</a> &raquo;</li>
    
      
        
          <li>广度优先遍历 &raquo;</li>
        
      
    
    <li>0126 word ladder ii</li>
    <li class="wy-breadcrumbs-aside">
      
    </li>
  </ul>
  
  <hr/>
</div>
          <div role="main">
            <div class="section">
              
                <ul>
<li><a href="https://leetcode-cn.com/problems/word-ladder-ii/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you--2/">题解链接</a></li>
</ul>
<h2 id="bfs">方法一：单向 BFS</h2>
<p>Java 代码：</p>
<pre><code class="java">import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;


public class Solution {

    /**
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public List&lt;List&lt;String&gt;&gt; findLadders(String beginWord, String endWord, List&lt;String&gt; wordList) {
        // 先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
        Set&lt;String&gt; wordSet = new HashSet&lt;&gt;(wordList);
        List&lt;List&lt;String&gt;&gt; res = new ArrayList&lt;&gt;();
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return res;
        }

        // 第 1 步：使用广度优先遍历得到后继结点列表 successors
        // key：字符串，value：广度优先遍历过程中 key 的后继结点列表
        Map&lt;String, Set&lt;String&gt;&gt; successors = new HashMap&lt;&gt;();
        boolean found = bfs(beginWord, endWord, wordSet, successors);
        if (!found) {
            return res;
        }

        // 第 2 步：基于后继结点列表 successors ，使用回溯算法得到所有最短路径列表
        Deque&lt;String&gt; path = new ArrayDeque&lt;&gt;();
        path.addLast(beginWord);
        dfs(beginWord, endWord, successors, path, res);
        return res;
    }

    private boolean bfs(String beginWord, String endWord, Set&lt;String&gt; wordSet,
                        Map&lt;String, Set&lt;String&gt;&gt; successors) {
        Queue&lt;String&gt; queue = new LinkedList&lt;&gt;();
        queue.offer(beginWord);

        // 标准写法，记录方法问过的单词
        Set&lt;String&gt; visited = new HashSet&lt;&gt;();
        visited.add(beginWord);

        boolean found = false;
        int wordLen = beginWord.length();
        // 当前层访问过的结点，当前层全部遍历完成以后，再添加到总的 visited 集合里
        Set&lt;String&gt; nextLevelVisited = new HashSet&lt;&gt;();
        while (!queue.isEmpty()) {
            int currentSize = queue.size();
            for (int i = 0; i &lt; currentSize; i++) {
                String currentWord = queue.poll();
                char[] charArray = currentWord.toCharArray();
                for (int j = 0; j &lt; wordLen; j++) {
                    char originChar = charArray[j];
                    for (char k = 'a'; k &lt;= 'z'; k++) {
                        if (charArray[j] == k) {
                            continue;
                        }
                        charArray[j] = k;
                        String nextWord = new String(charArray);
                        if (wordSet.contains(nextWord)) {
                            if (!visited.contains(nextWord)) {
                                if (nextWord.equals(endWord)) {
                                    found = true;
                                }

                                // 避免下层元素重复加入队列，这里感谢 https://leetcode-cn.com/u/zhao-da-ming/ 优化了这个逻辑
                                if (!nextLevelVisited.contains(nextWord)) {
                                    queue.offer(nextWord);
                                    nextLevelVisited.add(nextWord);
                                }

                                // 维护 successors 的定义
                                successors.computeIfAbsent(currentWord, a -&gt; new HashSet&lt;&gt;());
                                successors.get(currentWord).add(nextWord);
                            }
                        }
                    }
                    charArray[j] = originChar;
                }
            }

            if (found) {
                break;
            }
            visited.addAll(nextLevelVisited);
            nextLevelVisited.clear();
        }
        return found;
    }

    private void dfs(String beginWord, String endWord,
                     Map&lt;String, Set&lt;String&gt;&gt; successors,
                     Deque&lt;String&gt; path, List&lt;List&lt;String&gt;&gt; res) {
        if (beginWord.equals(endWord)) {
            res.add(new ArrayList&lt;&gt;(path));
            return;
        }

        if (!successors.containsKey(beginWord)) {
            return;
        }

        Set&lt;String&gt; successorWords = successors.get(beginWord);
        for (String nextWord : successorWords) {
            path.addLast(nextWord);
            dfs(nextWord, endWord, successors, path, res);
            path.removeLast();
        }
    }
}
</code></pre>

<h2 id="bfs_1">方法二：双向 BFS</h2>
<p>Java 代码：</p>
<pre><code class="java">import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution {

    public List&lt;List&lt;String&gt;&gt; findLadders(String beginWord, String endWord, List&lt;String&gt; wordList) {
        // 先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
        List&lt;List&lt;String&gt;&gt; res = new ArrayList&lt;&gt;();
        Set&lt;String&gt; wordSet = new HashSet&lt;&gt;(wordList);
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return res;
        }
        // 第 1 步：使用双向广度优先遍历得到后继结点列表 successors
        // key：字符串，value：广度优先遍历过程中 key 的后继结点列表
        Map&lt;String, Set&lt;String&gt;&gt; successors = new HashMap&lt;&gt;();
        boolean found = bidirectionalBfs(beginWord, endWord, wordSet, successors);
        if (!found) {
            return res;
        }
        // 第 2 步：基于后继结点列表 successors ，使用回溯算法得到所有最短路径列表
        Deque&lt;String&gt; path = new ArrayDeque&lt;&gt;();
        path.addLast(beginWord);
        dfs(beginWord, endWord, successors, path, res);
        return res;
    }

    private boolean bidirectionalBfs(String beginWord,
                                     String endWord,
                                     Set&lt;String&gt; wordSet,
                                     Map&lt;String, Set&lt;String&gt;&gt; successors) {
        // 记录访问过的单词
        Set&lt;String&gt; visited = new HashSet&lt;&gt;();
        visited.add(beginWord);
        visited.add(endWord);

        Set&lt;String&gt; beginVisited = new HashSet&lt;&gt;();
        beginVisited.add(beginWord);
        Set&lt;String&gt; endVisited = new HashSet&lt;&gt;();
        endVisited.add(endWord);

        int wordLen = beginWord.length();
        boolean forward = true;
        boolean found = false;
        // 在保证了 beginVisited 总是较小（可以等于）大小的集合前提下，&amp;&amp; !endVisited.isEmpty() 可以省略
        while (!beginVisited.isEmpty() &amp;&amp; !endVisited.isEmpty()) {
            // 一直保证 beginVisited 是相对较小的集合，方便后续编码
            if (beginVisited.size() &gt; endVisited.size()) {
                Set&lt;String&gt; temp = beginVisited;
                beginVisited = endVisited;
                endVisited = temp;

                // 只要交换，就更改方向，以便维护 successors 的定义
                forward = !forward;
            }
            Set&lt;String&gt; nextLevelVisited = new HashSet&lt;&gt;();
            // 默认 beginVisited 是小集合，因此从 beginVisited 出发
            for (String currentWord : beginVisited) {
                char[] charArray = currentWord.toCharArray();
                for (int i = 0; i &lt; wordLen; i++) {
                    char originChar = charArray[i];
                    for (char j = 'a'; j &lt;= 'z'; j++) {
                        if (charArray[i] == j) {
                            continue;
                        }
                        charArray[i] = j;
                        String nextWord = new String(charArray);
                        if (wordSet.contains(nextWord)) {
                            if (endVisited.contains(nextWord)) {
                                found = true;
                                // 在另一侧找到单词以后，还需把这一层关系添加到「后继结点列表」
                                addToSuccessors(successors, forward, currentWord, nextWord);
                            }

                            if (!visited.contains(nextWord)) {
                                nextLevelVisited.add(nextWord);
                                addToSuccessors(successors, forward, currentWord, nextWord);
                            }
                        }
                    }
                    charArray[i] = originChar;
                }
            }
            beginVisited = nextLevelVisited;
            visited.addAll(nextLevelVisited);
            if (found) {
                break;
            }
        }
        return found;
    }

    private void dfs(String beginWord,
                     String endWord,
                     Map&lt;String, Set&lt;String&gt;&gt; successors,
                     Deque&lt;String&gt; path,
                     List&lt;List&lt;String&gt;&gt; res) {

        if (beginWord.equals(endWord)) {
            res.add(new ArrayList&lt;&gt;(path));
            return;
        }

        if (!successors.containsKey(beginWord)) {
            return;
        }

        Set&lt;String&gt; successorWords = successors.get(beginWord);
        for (String successor : successorWords) {
            path.addLast(successor);
            dfs(successor, endWord, successors, path, res);
            path.removeLast();
        }
    }

    private void addToSuccessors(Map&lt;String, Set&lt;String&gt;&gt; successors, boolean forward,
                                 String currentWord, String nextWord) {
        if (!forward) {
            String temp = currentWord;
            currentWord = nextWord;
            nextWord = temp;
        }

        // Java 1.8 以后支持
        successors.computeIfAbsent(currentWord, a -&gt; new HashSet&lt;&gt;());
        successors.get(currentWord).add(nextWord);
    }
}
</code></pre>
              
            </div>
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="../0127-word-ladder/" class="btn btn-neutral float-right" title="0127 word ladder">Next <span class="icon icon-circle-arrow-right"></span></a>
      
      
        <a href="../.." class="btn btn-neutral" title="Welcome to MkDocs"><span class="icon icon-circle-arrow-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <!-- Copyright etc -->
    
  </div>

  Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/snide/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
      
        </div>
      </div>

    </section>

  </div>

  <div class="rst-versions" role="note" aria-label="versions">
    <span class="rst-current-version" data-toggle="rst-current-version">
      
      
        <span><a href="../.." style="color: #fcfcfc;">&laquo; Previous</a></span>
      
      
        <span style="margin-left: 15px"><a href="../0127-word-ladder/" style="color: #fcfcfc">Next &raquo;</a></span>
      
    </span>
</div>
    <script>var base_url = '../..';</script>
    <script src="../../js/theme.js" defer></script>
      <script src="../../js/extra.js" defer></script>
      <script src="../../js/baidu-tongji.js" defer></script>
      <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
      <script src="../../search/main.js" defer></script>
    <script defer>
        window.onload = function () {
            SphinxRtdTheme.Navigation.enable(true);
        };
    </script>

</body>
</html>
